多数元素

发表于 | 分类于 |
字数统计: 868 字 | 阅读时长 ≈ 3 分钟

题目描述：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
输入：[3,2,3]
输出：3

示例 2：
输入：[2,2,1,1,1,2,2]
输出：2

进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

哈希表 + 计数类型

  • 声明一个计数器,也就是一个对象 const map = {}
  • 遍历字符串，开始记数，如果字符串的字母第一次碰见，map[第一次碰见的字母] = 1
  • 如果map已经记录过这个字母，则 map[记录过的的字母] += 1
  • 在遍历的过程中，看 map[记录过的的字母] 是否大于 数组总长度/2
1
2
3
4
5
6
7
8
var majorityElement = function(nums) {
  let half = nums.length / 2
  let obj = {}
  for(let num of nums){
    obj[num] = (obj[num] || 0) + 1
    if(obj[num] > half) return num
  }
};

复杂度分析

  • 时间复杂度：O(N)，其中 N 为数组的长度
  • 空间复杂度：O(N)，其中 N 为数组的长度

执行结果：通过

  • 执行用时：68 ms, 在所有 JavaScript 提交中击败了92.96%的用户
  • 内存消耗：41.7 MB, 在所有 JavaScript 提交中击败了28.92%的用户

排序

既然数组中有出现次数> ⌊ n/2 ⌋的元素，那排好序之后的数组中，相同元素总是相邻的。
即存在长度> ⌊ n/2 ⌋的一长串 由相同元素构成的连续子数组。

举个例子：
无论是1 1 1 2 3，0 1 1 1 2 还是 -1 0 1 1 1，数组中间的元素总是“多数元素”，毕竟它长度> ⌊ n/2 ⌋

1
2
3
4
var majorityElement = function(nums) {
  nums.sort()
  return nums[nums.length >> 1]
};

复杂度分析

  • 时间复杂度：O(nlogn)。将数组排序的时间复杂度为O(nlogn)。

  • 空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。

执行结果：通过

  • 执行用时：56 ms, 在所有 JavaScript 提交中击败了99.76%的用户
  • 内存消耗：41.8 MB, 在所有 JavaScript 提交中击败了26.24%的用户

摩尔投票法

核心：对拼消耗，前提是一定有众数

玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。

  • ？》
1
2
3
4
5
6
7
8
9
10
11
var majorityElement = function(nums) {
  let res = nums[0], count = 1;
  for(let i = 0; i < nums.length; i++) {
    res === nums[i] ? count++ :count--;
    if(count === 0) {
      res = nums[i];
      count = 1;
    }
  }
  return res;
};

复杂度分析

  • 时间复杂度：O(N)，其中 N 为数组的长度
  • 空间复杂度：O(1)

执行结果：通过

  • 执行用时：56 ms, 在所有 JavaScript 提交中击败了99.76%的用户
  • 内存消耗：39.8 MB, 在所有 JavaScript 提交中击败了85.36%的用户